package com.c2b.algorithm.leetcode.base;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * <a href='https://leetcode.cn/problems/design-front-middle-back-queue/'>设计前中后队列(Design Front Middle Back Queue)</a>
 * <p>请你设计一个队列，支持在前，中，后三个位置的 push 和 pop 操作。</p>
 * <p>
 * 请你完成 FrontMiddleBack 类：
 *     <ul>
 *         <li>FrontMiddleBack() 初始化队列。</li>
 *         <li>void pushFront(int val) 将 val 添加到队列的 最前面 。</li>
 *         <li>void pushMiddle(int val) 将 val 添加到队列的 正中间 。</li>
 *         <li>void pushBack(int val) 将 val 添加到队里的 最后面 。</li>
 *         <li>int popFront() 将 最前面 的元素从队列中删除并返回值，如果删除之前队列为空，那么返回 -1 。</li>
 *         <li>int popMiddle() 将 正中间 的元素从队列中删除并返回值，如果删除之前队列为空，那么返回 -1 。</li>
 *         <li>int popBack() 将 最后面 的元素从队列中删除并返回值，如果删除之前队列为空，那么返回 -1 。</li>
 *     </ul>
 *     请注意当有 两个 中间位置的时候，选择靠前面的位置进行操作。比方说：
 *     <ul>
 *         <li>将 6 添加到 [1, 2, 3, 4, 5] 的中间位置，结果数组为 [1, 2, 6, 3, 4, 5] 。</li>
 *         <li>从 [1, 2, 3, 4, 5, 6] 的中间位置弹出元素，返回 3 ，数组变为 [1, 2, 4, 5, 6] 。</li>
 *     </ul>
 * </p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *
 *      输入：
 *          ["FrontMiddleBackQueue", "pushFront", "pushBack", "pushMiddle", "pushMiddle", "popFront", "popMiddle", "popMiddle", "popBack", "popFront"]
 *          [[], [1], [2], [3], [4], [], [], [], [], []]
 *      输出：
 *          [null, null, null, null, null, 1, 3, 4, 2, -1]
 *
 *      解释：
 *          FrontMiddleBackQueue q = new FrontMiddleBackQueue();
 *          q.pushFront(1);   // [1]
 *          q.pushBack(2);    // [1, 2]
 *          q.pushMiddle(3);  // [1, 3, 2]
 *          q.pushMiddle(4);  // [1, 4, 3, 2]
 *          q.popFront();     // 返回 1 -> [4, 3, 2]
 *          q.popMiddle();    // 返回 3 -> [4, 2]
 *          q.popMiddle();    // 返回 4 -> [2]
 *          q.popBack();      // 返回 2 -> []
 *          q.popFront();     // 返回 -1 -> [] （队列为空）
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 *  <ul>
 *      <li>1 <= val <= 10^9</li>
 *      <li>最多调用 1000 次 pushFront， pushMiddle， pushBack， popFront， popMiddle 和 popBack 。</li>
 *  </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/12/11 11:37
 */
public class LC1670DesignFrontMiddleBackQueue_M {

    static class FrontMiddleBackQueue {
        List<Integer> valList;

        public FrontMiddleBackQueue() {
            valList = new ArrayList<>();
        }

        public void pushFront(int val) {
            valList.add(0, val);
            //System.out.printf("将%s添加到队列的最前面,valList：%s%n", val, valList);
        }

        public void pushMiddle(int val) {
            valList.add(valList.size() >> 1, val);
            //System.out.printf("将%s添加到队列的正中间,valList：%s%n", val, valList);
        }

        public void pushBack(int val) {
            valList.add(valList.size(), val);
            //System.out.printf("将%s添加到队列的最后面,valList：%s%n", val, valList);
        }

        public int popFront() {
            if (valList.isEmpty()) {
                return -1;
            }
            return valList.remove(0);
        }

        public int popMiddle() {
            if (valList.isEmpty()) {
                return -1;
            }
            return valList.remove((valList.size() - 1) >> 1);
        }

        public int popBack() {
            if (valList.isEmpty()) {
                return -1;
            }
            return valList.remove(valList.size() - 1);
        }
    }

    static class FrontMiddleBackQueue2 {
        Deque<Integer> firstHalf;
        Deque<Integer> secondHalf;

        public FrontMiddleBackQueue2() {
            firstHalf = new LinkedList<>();
            secondHalf = new LinkedList<>();
        }

        public void pushFront(int val) {
            firstHalf.addFirst(val);
            if (firstHalf.size() == secondHalf.size() + 2) {
                secondHalf.addFirst(firstHalf.removeLast());
            }
        }

        public void pushMiddle(int val) {
            if (firstHalf.size() == secondHalf.size() + 1) {
                secondHalf.addFirst(firstHalf.removeLast());
            }
            firstHalf.addLast(val);
        }

        public void pushBack(int val) {
            secondHalf.addLast(val);
            if (firstHalf.size() + 1 == secondHalf.size()) {
                firstHalf.addLast(secondHalf.removeFirst());
            }
        }

        public int popFront() {
            if (firstHalf.isEmpty()) {
                return -1;
            }
            int val = firstHalf.removeFirst();
            if (firstHalf.size() + 1 == secondHalf.size()) {
                firstHalf.addLast(secondHalf.removeFirst());
            }
            return val;
        }

        public int popMiddle() {
            if (firstHalf.isEmpty()) {
                return -1;
            }
            int remove = firstHalf.removeLast();
            if (firstHalf.size() + 1 == secondHalf.size()) {
                firstHalf.addLast(secondHalf.removeFirst());
            }
            return remove;
        }

        public int popBack() {
            if (firstHalf.isEmpty()) {
                return -1;
            }
            // 特殊情况：需要从后半段尾部移除一个元素，若后半段元素个数为0，则需要从前半段移除
            if (secondHalf.isEmpty()) {
                return firstHalf.removeLast();
            }
            int remove = secondHalf.removeLast();
            if (firstHalf.size() == secondHalf.size() + 2) {
                secondHalf.addFirst(firstHalf.removeLast());
            }
            return remove;
        }
    }

    public static void main(String[] args) {
        FrontMiddleBackQueue2 frontMiddleBackQueue = new FrontMiddleBackQueue2();
        frontMiddleBackQueue.pushFront(1);
        frontMiddleBackQueue.pushBack(2);
        frontMiddleBackQueue.pushMiddle(3);
        frontMiddleBackQueue.pushMiddle(4);
        System.out.println(frontMiddleBackQueue.popFront());
        System.out.println(frontMiddleBackQueue.popMiddle());
        System.out.println(frontMiddleBackQueue.popMiddle());
        System.out.println(frontMiddleBackQueue.popBack());
        System.out.println(frontMiddleBackQueue.popFront());
    }
}
